﻿/*
哈希
	哈希又称散列，一种组织数据的方式，本质是通过哈希函数把关键字key跟存储位置建立一个映射关系，
	查找时通过哈希函数计算出key存储的位置，进行快速查找

方法：
	1.直接定址法
		当关键字的范围(比较集中)时，直接定址法就是非常简单高效的方法，⽐如一组关键字都在[0,99]之间，
		那么开一个100个数的数组，每个关键字的值直接就是存储位置的下标。再比如一组关键字值都在[a,z]
		的⼩写字母，那么开一个26个数的数组，每个关键字acsii码  -a   ascii码就是存储位置的下标。
	直接定址法本质就是：用关键字计算出一个绝对位置或者相对位置。    譬如：力扣     字符串中第一个唯一字符

	直接定址法的缺点也非常明显，当关键字的范围比较分散时，就很浪费内存甚至内存不够用。假设只有数据范围是[0,9999]
	的N个值，我们要映射到一个M个空间的数组中(一般情况下M >= N)，那么就要借助哈希函数(hash function)hf，关键字key
	被放到数组的h(key)位置，这要注意的是h(key) 计算出的值必须在[0,M)之间。

	当然会导致一个问题：两个不同的key可能会映射到同⼀个位置去，这种问题叫：哈希冲突/哈希碰撞。
						理想情况是找出一个好的哈希函数避免冲突，但是实际场景中，冲突不可避免
					
负载因子：
	假设哈希表中已经映射存储了N个值，哈希表的大⼩为M，那么 ，负载因子有些地方也翻译为载荷因子/装载因子等，
	英文为load factor。
	负载因子越大，哈希冲突的概率越高，空间利用率越高；负载因子越⼩，哈希冲突的概率越低，空间利用率越低； 

将关键字转为整数：
	将关键字映射到数组中位置，一般是整数好做映射计算，如果不是整数，我们要想办法转换成整数，
	哈希函数部分如果关键字不是整数，那么讨论的Key是关键字转换成的整数。


哈希函数
好的哈希函数应该让N个关键字被等概率的均匀的散列分布到哈希表的M个空间中，但是实际中却很难做到
	1.除留余数法 / 除法散列法
		  除法散列法也叫做除留余数法，假设哈希表的大⼩为M，那么通过key除以M的余数作为映射位置的下标，
		  也就是哈希函数为：h(key)= key % M
	  除法散列法时，要尽量避免M为某些值，如2的幂，10的幂等
	  如果是2^X ，那么key % 2^X 本质相当于保留key的后X位，那么后x位相同的值，计算出的哈希值都是一样的，就冲突了

  * 当使用除法散列法时，建议M取不太接近2的整数次幂的一个质数(素数)
	
	与运算  保留最后的多少位就 左移(多少位+1)位  后 -1
	int hashi = key & (1<<17 - 1)      意思为：左移十七位 - 1         保留最后的十六位 


处理哈希冲突
	实践中哈希表一般还是选择除法散列法作为哈希函数，当然哈希表无论选择什么哈希函数也避免不了
	冲突，那么插入数据时，如何解决冲突？
	主要有两种两种方法：开放定址法和链地址法。

	开放定址法
		在开放定址法中所有的元素都放到哈希表里，当一个关键字key用哈希函数计算出的位置冲突了，则按
		照某种规则找到一个没有存储数据的位置进行存储，开放定址法中负载因子一定是⼩于的。这里的规则
		有三种：线性探测、二次探测、双重探测。

	自定义类型和string都不能自动转换成为整型
	如果是非常常见和常用的类  再进行特化（譬如string）
	但是自定义类型  不常用的  譬如：日期类     这种情况就可以传仿函数


unordered_map   的使用对key有什么要求？
要求是：要满足哈希和相等比较的要求   要有个哈希函数还得能用 == 比较   也就是能算哈希值且能比较的

当不支持比较整型和等于的比较    就写个仿函数传过去支持   



乘法散列法
	乘法散列法对哈希表大⼩M没有要求，用关键字 K 乘上常数 A(0<A<1)，并抽取出 k*A 的⼩数部分。
	第二步：后再用M乘以 k*A 的⼩数部分，再向下取整

	h(key)= floor(M x((A x key)%1.0))其中floor表示对表达式进行下取整，A∈(0,1)，这里最重要的是A的值应该如何设定
	A=(根5 - 1)/2=0.6180339887...(黄金分割点]

	乘法散列法对哈希表大⼩M是没有要求的 假设M为1024，key为1234，A=0.6180339887, A*key = 762.6539420558，
	取⼩数部分为0.6539420558, M×((A×key)%1.0)= 0.6539420558 * 1024=669.6366651392，那么h(1234) = 669



全域散列法
	如果存在一个恶意的对手，他针对我们提供的散列函数，特意构造出一个发生严重冲突的数据集，
	比如，让所有关键字全部落入同一个位置中。这种情况是可以存在的，只要散列函数是公开且确定
	的，就可以实现此攻击。解决方法自然是⻅招拆招，给散列函数增加随机性，攻击者就无法找出确
	定可以导致最坏情况的数据。这种方法叫做全域散列

	h ab(key) = ((a × key + b)%P )%M
	 P需要选一个足够大的质数，a可以随机选[1,P-1]之间的任意整数，b可以随机选[0,P-1]之间的任意整数，
	 这些函数构成了⼀个P*(P-1)组全域散列函数组。假设P=17，M=6，a=3，b=4
	
	h 34 (8) = ((3 × 8 + 4)%17)%6  =  5

	要注意的是每次初始化哈希表时，随机选取全域散列函数组中的一个散列函数使用，后续增删查
	改都固定使用这个散列函数，否则每次哈希都是随机选一个散列函数，那么插入是一个散列函数，
	查找又是另一个散列函数，就会导致找不到插入的key了


开放定址法（无法解决冲突和利用率低的问题）
	扩容：开放定址法负载因子必须小于1，链地址法的负载因子没有限制，可以大于1。
		  负载因子越大，哈希冲突的概率越高，空间利用率越高；负载因子越小，哈希冲突概率越低，空间利用率也越低；
		  STL中   unordered_xxx 的最大负载因子基本控制在1，大于1就扩容





*/